package leetcode;

import common.ListNode;
import common.Util;

/**
 * 双链表实现
 * @link{https://leetcode-cn.com/problems/design-linked-list/}
 */
public class LeetCode707_2 {
    /**
     * 哨兵头节点
     */
    public ListNode head;
    /**
     * 哨兵尾节点
     */
    public ListNode tail;
    /**
     * 单链表的大小
     */
    public int size;

    public LeetCode707_2() {
        this.head = new ListNode(0);
        this.tail = new ListNode(0);
        head.next = tail;
        tail.prev = head;
        this.size = 0;
    }

    /**
     * Get the value of the index-th node in the linked list. If the index is
     * invalid, return -1.
     */
    public int get(int index) {
        if (index < 0 || size == 0 || index > size - 1) return -1;
        if (index < size / 2) return getFromHead(index);
        if (index >= size / 2) return getFromTail(index);
        return -1;
    }

    public int getFromHead(int index) {
        ListNode cur = head.next;
        for (int i = 0; i < index; i++) cur = cur.next;
        return cur.val;
    }

    public int getFromTail(int index) {
        ListNode cur = tail;
        for (int i = size; i > index; i--) cur = cur.prev;
        return cur.val;
    }

    /**
     * Add a node of value val before the first element of the linked list. After
     * the insertion, the new node will be the first node of the linked list.
     */
    public void addAtHead(int val) {
        ListNode toAddNode = new ListNode(val);
        ListNode next = this.head.next;
        this.head.next = toAddNode;
        toAddNode.prev = this.head;
        toAddNode.next = next;
        next.prev = toAddNode;
        this.size++;
    }

    /** Append a node of value val to the last element of the linked list. */
    public void addAtTail(int val) {
        ListNode toAddNode = new ListNode(val);
        ListNode prev = this.tail.prev;
        this.tail.prev = toAddNode;
        toAddNode.next = this.tail;
        toAddNode.prev = prev;
        prev.next = toAddNode;
        this.size++;
    }

    /**
     * Add a node of value val before the index-th node in the linked list. If index
     * equals to the length of linked list, the node will be appended to the end of
     * linked list. If index is greater than the length, the node will not be
     * inserted.
     */
    public void addAtIndex(int index, int val) {
        if (index < 0 || index > size) return;
        if (index < size / 2) {
            addFromHead(index, val);
        } else {
            addFromTail(index, val); 
        }
    }

    private void addFromHead(int index, int val) {
        ListNode toAddNode = new ListNode(val);
        ListNode prev = head;
        for (int i = 0; i < index; i++) prev = prev.next;
        toAddNode.next = prev.next;
        toAddNode.prev = prev;
        prev.next.prev = toAddNode;
        prev.next = toAddNode;
        this.size++;
    }

    // ok
    private void addFromTail(int index, int val) {
        ListNode toAddNode = new ListNode(val);
        // 插入节点的后继节点
        ListNode node = tail;
        for (int i = size; i > index; i--) node = node.prev;
        toAddNode.prev = node.prev;
        toAddNode.next = node;
        node.prev.next = toAddNode;
        node.prev = toAddNode;
        this.size++;
    }

    /** Delete the index-th node in the linked list, if the index is valid. */
    public void deleteAtIndex(int index) {
        if (index < 0 || size == 0 || index > size - 1) return;
        if (index < size / 2) {
            deleteFromHead(index);
        } else {
            deleteFromTail(index);
        } 
    }

    public void deleteFromHead(int index) {
        // 要删除节点的前继节点
        ListNode prev = head;
        for (int i = 0; i < index; i++) prev = prev.next;
        prev.next = prev.next.next;
        prev.next.prev = prev;
        this.size--;
    }

    // ok
    public void deleteFromTail(int index) {
        // 要删除的节点
        ListNode next = tail;
        for (int i = size; i > index; i--) next = next.prev;
        next.prev.next = next.next;
        next.next.prev = next.prev;
        this.size--;
    }

    public static void main(String[] args) {
        LeetCode707_2 linkedList = new LeetCode707_2();

        linkedList.addAtHead(31); // 0 <-> 1 <-> 0
        System.out.println(Util.formatListNode(linkedList.head));

        linkedList.addAtHead(40); // 0 <-> 1 <-> 0
        System.out.println(Util.formatListNode(linkedList.head));

        linkedList.addAtHead(7); // 0 <-> 1 <-> 0
        System.out.println(Util.formatListNode(linkedList.head));

        linkedList.addAtHead(94); // 0 <-> 1 <-> 0
        System.out.println(Util.formatListNode(linkedList.head));

        linkedList.addAtTail(60); // 0 <-> 1 <-> 0
        System.out.println(Util.formatListNode(linkedList.head));

        linkedList.addAtTail(9); // 0 <-> 1 <-> 0
        System.out.println(Util.formatListNode(linkedList.head));

        linkedList.deleteAtIndex(2); // 0 <-> 1 <-> 0
        System.out.println(Util.formatListNode(linkedList.head));

       



    }
}